package DataStructrue;

import java.util.ArrayList;
import java.util.List;
//递归算法:分治,将问题分为若干子问题求解;回溯,枚举方案树的所有分支;
public class Recurse {
    static int[] arr= new int[]{1,2,3};
    static boolean[] mark=new boolean[arr.length];//是否已选择
    static List<Integer> l=new ArrayList<>();//选择方案
    static int lim=3;//可重复选择时的最大选择数量

    public static void main(String[] args) {
        enumCC1(0);
    }
    //无重复排列方案
    public static void enumA(){
        System.out.println(l);
        for (int i = 0; i < arr.length; i++) {
            if(mark[i])
                continue;
            l.add(arr[i]);
            mark[i]=true;
            enumA();
            l.remove(l.size()-1);
            mark[i]=false;
        }
    }
    //可重复排列方案
    public static void enumAA(){
        if(l.size()==lim){
            System.out.println(l);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            l.add(arr[i]);
            enumAA();
            l.remove(l.size()-1);
        }
    }
    //无重复组合方案,无重复排列方案去重(无序化)
    public static void enumC(int idx){
        System.out.println(l);
        for (int i = idx; i < arr.length; i++) {
            l.add(arr[i]);
            enumC(i+1);
            l.remove(l.size()-1);
        }
    }
    //无重复组合方案
    public static void enumC1(int idx){
        if(idx==arr.length) {
            System.out.println(l);
            return;
        }
        //不选择或者选择
        enumC1(idx+1);
        l.add(arr[idx]);
        enumC1(idx+1);
        l.remove(l.size()-1);
    }
    //可重复组合方案,可重复排列方案去重(无序化)
    public static void enumCC(int idx){
        if(l.size()==lim){
            System.out.println(l);
            return;
        }
        for (int i = idx; i < arr.length; i++) {
            l.add(arr[i]);
            enumCC(i);
            l.remove(l.size()-1);
        }
    }
    //可重复组合方案
    public static void enumCC1(int idx){
        if(idx==arr.length||l.size()==lim){
            System.out.println(l);
            return;
        }
        //不选择或者选择
        enumCC1(idx+1);
        l.add(arr[idx]);
        enumCC1(idx);//选择后还可选择
        l.remove(l.size()-1);
    }


}
